package com.chilly.linkedlist;

import java.util.HashSet;
import java.util.Set;

/**
 * 141. 环形链表
 * 给定一个链表，判断链表中是否有环。
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。
 * <p>
 * Created by Chilly Cui on 2020/11/30.
 */
public class LinkedListCycle {
    public static void main(String[] args) {

    }

    static class Solution {

        /**
         * 方法二：快慢指针
         * <p>
         * 【龟兔赛跑算法】: [兔子」跑得快，「乌龟」跑得慢;
         * 当「乌龟」和「兔子」从链表上的同一个节点开始移动时，
         * 如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；
         * 如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动
         * 等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。
         * <p>
         * so
         * 定义两个指针，一快一满。
         * 慢指针每次只移动一步，而快指针每次移动两步。
         * 初始时，慢指针在位置 head，而快指针在位置 head.next
         */
        public boolean hasCycle(ListNode head) {
            if (head == null || head.next == null)
                return false;

            ListNode slow = head;
            ListNode fast = head.next;
            while (slow != fast){
                if (fast == null || fast.next == null){
                    return false;
                }
                slow = slow.next;
                fast = fast.next.next;
            }

            return true;
        }

        /*//方法一：哈希表
        //最容易想到的方法是遍历所有节点，每次遍历到一个节点时，判断该节点此前是否被访问过。
        //使用哈希表来存储所有已经访问过的节点
        //如果该节点已经存在于哈希表中，则说明该链表是环形链表，否则就将该节点加入哈希表中
        //重复这一过程，直到我们遍历完整个链表即可。
        public boolean hasCycle(ListNode head) {
            Set<ListNode> set = new HashSet<>();
            while (head != null){
                boolean b = set.add(head);
                if (!b){
                    return true;
                }
                head = head.next;
            }
            return false;
        }*/
    }

    static class ListNode {
        int val;
        ListNode next;

        public ListNode(int val) {
            this.val = val;
            next = null;
        }
    }
}
